// @FileName  :sort.c
// @Time      :2024/5/20 16:58
// @Author    :YKW
//# include <bits/stdc++.h>
//using namespace std;
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <string.h>
# include <stdlib.h>

int n, cho, k[200], t[250], ans;

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int cmp(const void *x, const void *y) {
    return (*(int *) x) - (*(int *) y);
}

//堆排序
void adjust(int i, int n) {
    int j, temp;
    temp = k[i];
    j = 2 * i + 1;
    while (j < n) {
        ans++;
        if (j < n - 1 && k[j] < k[j + 1])
            j++;
        if (temp >= k[j])
            break;
        k[(j - 1) / 2] = k[j];
        j = 2 * j + 1;
    }
    k[(j - 1) / 2] = temp;
}

void merge(int l1, int r1, int l2, int r2) {
    int i = l1, j = l2, q = l1;
    while (i <= r1 && j <= r2) {
        ans++;
        if (k[i] <= k[j]) t[q++] = k[i++];
        else t[q++] = k[j++];
    }
    while (i <= r1) t[q++] = k[i++];
    while (j <= r2) t[q++] = k[j++];
    for (int p = l1; p <= r2; p++) k[p] = t[p];
}

void merge_sort(int l, int r) {
    int m = (l + r) / 2;
    if (l < r) {
        merge_sort(l, m);
        merge_sort(m + 1, r);
        merge(l, m, m + 1, r);
    }
}

void quickSort(int left, int right) {
    int i, last;
    if (left < right) {
        last = left;
        for (i = left + 1; i <= right; i++) {
            ans++;
            if (k[i] < k[left])
                swap(&k[++last], &k[i]);
        }
        swap(&k[left], &k[last]);
        quickSort(left, last - 1);
        quickSort(last + 1, right);
    }
}

int main() {
    scanf("%d%d", &n, &cho);
    for (int i = 0; i < n; i++)
        scanf("%d", &k[i]);
    switch (cho) {
        case 1: //选择排序
            qsort(k, n, sizeof(int), cmp);
            ans = n * (n - 1) / 2;
            break;
        case 2://冒泡排序
            for (int i = n - 1; i >= 0; i--) {
                int flag = 0;
                for (int j = 0; j < i; j++) {
                    ans++;
                    if (k[j] > k[j + 1]) {
                        flag = 1;
                        swap(&k[j], &k[j + 1]);
                    }
                }
                if (flag == 0)break;
            }
            break;
        case 3://堆排序
            for (int i = n / 2 - 1; i >= 0; i--) {
                adjust(i, n);
            }
            for (int i = n; i > 0; i--) {
                swap(k + i - 1, k);
                adjust(0, i - 1);
            }
            qsort(k, n, sizeof(int), cmp);
            break;
        case 4://二路归并
            merge_sort(0, n - 1);
            break;
        case 5://快排
            quickSort(0, n - 1);
            break;
    }
    for (int i = 0; i < n; i++)printf("%d ", k[i]);
    printf("\n%d", ans);
}